home *** CD-ROM | disk | FTP | other *** search
/ C++ für Kids / C++ for kids.iso / SETUP / US / CBUILDER / DATA.Z / DEQUE.H < prev    next >
C/C++ Source or Header  |  1997-02-13  |  31KB  |  993 lines
  1. /* $Revision:   8.1  $ */
  2.  
  3. /***************************************************************************
  4.  *
  5.  * deque - Declaration and definition for the Standard Library deque class
  6.  *
  7.  * $Id: deque,v 1.43 1995/09/29 04:16:00 hart Exp $
  8.  *
  9.  ***************************************************************************
  10.  *
  11.  * Copyright (c) 1994
  12.  * Hewlett-Packard Company
  13.  *
  14.  * Permission to use, copy, modify, distribute and sell this software
  15.  * and its documentation for any purpose is hereby granted without fee,
  16.  * provided that the above copyright notice appear in all copies and
  17.  * that both that copyright notice and this permission notice appear
  18.  * in supporting documentation.  Hewlett-Packard Company makes no
  19.  * representations about the suitability of this software for any
  20.  * purpose.  It is provided "as is" without express or implied warranty.
  21.  *
  22.  *
  23.  ***************************************************************************
  24.  *
  25.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  26.  * ALL RIGHTS RESERVED
  27.  *
  28.  * The software and information contained herein are proprietary to, and
  29.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  30.  * intends to preserve as trade secrets such software and information.
  31.  * This software is furnished pursuant to a written license agreement and
  32.  * may be used, copied, transmitted, and stored only in accordance with
  33.  * the terms of such license and with the inclusion of the above copyright
  34.  * notice.  This software and information or any other copies thereof may
  35.  * not be provided or otherwise made available to any other person.
  36.  *
  37.  * Notwithstanding any other lease or license that may pertain to, or
  38.  * accompany the delivery of, this computer software and information, the
  39.  * rights of the Government regarding its use, reproduction and disclosure
  40.  * are as set forth in Section 52.227-19 of the FARS Computer
  41.  * Software-Restricted Rights clause.
  42.  *
  43.  * Use, duplication, or disclosure by the Government is subject to
  44.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  45.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  46.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  47.  * P.O. Box 2328, Corvallis, Oregon 97339.
  48.  *
  49.  * This computer software and information is distributed with "restricted
  50.  * rights."  Use, duplication or disclosure is subject to restrictions as
  51.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  52.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  53.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  54.  * then the "Alternate III" clause applies.
  55.  *
  56.  **************************************************************************/
  57.  
  58. #ifndef __STD_DEQUE__
  59. #define __STD_DEQUE__
  60.  
  61. #include <stddefs.h>
  62.  
  63. #include <stdcomp.h>
  64. #include <function>
  65. #include <algorith>
  66. #include <iterator>
  67.  
  68. #ifndef Allocator
  69. #define Allocator allocator
  70. #include <memory>
  71. #endif
  72.  
  73. #ifndef deque
  74. #define deque deque
  75. #endif
  76.  
  77. #ifndef RWSTD_NO_NAMESPACE
  78. namespace std {
  79. #endif
  80.  
  81. template <class T>
  82. class  deque
  83. {
  84.   public:
  85.  
  86.     class  iterator;
  87.     class  const_iterator;
  88.     friend class iterator;
  89.     friend class const_iterator;
  90.  
  91.   public:
  92.  
  93.     typedef T                             value_type;
  94.     typedef Allocator<T>                  data_allocator_type;
  95.     typedef Allocator<T>::pointer         pointer;
  96.     typedef Allocator<T>::reference       reference;
  97.     typedef Allocator<T>::const_reference const_reference;
  98.     typedef Allocator<T>::size_type       size_type;
  99.     typedef Allocator<T>::difference_type difference_type;
  100.     typedef Allocator<pointer>            map_allocator_type;
  101.  
  102.   protected:
  103.  
  104.     data_allocator_type data_allocator;
  105.     map_allocator_type  map_allocator;
  106.  
  107.     typedef Allocator<pointer>::pointer map_pointer;
  108.  
  109.     static size_type buffer_size ()
  110.     {
  111.         //
  112.         // Each time we allocate memory we reserve space for
  113.         // a chunk of objects of type T.  This is currently tuned to
  114.         // allocate memory in 1K chunks, except for large objects.
  115.         //
  116.         return sizeof(T) >= 1024 ? 1 : 1024 / sizeof(T);
  117.     }
  118.  
  119.   public:
  120.     //
  121.     // Definition of our iterator.
  122.     //
  123.     class iterator : public random_access_iterator<T, difference_type>
  124.     {
  125.         friend class deque<T>;
  126.         friend class const_iterator;
  127.  
  128.       protected:
  129.  
  130.         pointer     current;
  131.         pointer     first;
  132.         pointer     last;
  133.         map_pointer node;
  134.  
  135.         iterator (pointer x, map_pointer y)
  136.             : current(x), first(*y), last(*y + buffer_size()), node(y) {}
  137.  
  138.       public:
  139.  
  140.         iterator () : current(0), first(0), last(0), node(0) {}
  141.         reference operator* () const { return *current; }
  142.         difference_type operator- (const iterator& x) const
  143.         {
  144.             return node == x.node
  145.                 ? current - x.current
  146.                 : difference_type(buffer_size() * (node - x.node - 1) +
  147.                                   (current - first) + (x.last - x.current));
  148.         }
  149.         iterator& operator++ ()
  150.         {
  151.             if (++current == last)
  152.             {
  153.                 first = *(++node);
  154.                 current = first;
  155.                 last = first + buffer_size();
  156.             }
  157.             return *this;
  158.         }
  159.         iterator operator++ (int)
  160.         {
  161.             iterator tmp = *this; ++*this; return tmp;
  162.         }
  163.         iterator& operator-- ()
  164.         {
  165.             if (current == first)
  166.             {
  167.                 first = *(--node);
  168.                 last = first + buffer_size();
  169.                 current = last;
  170.             }
  171.             --current;
  172.             return *this;
  173.         }
  174.         iterator operator-- (int)
  175.         {
  176.             iterator tmp = *this; --*this; return tmp;
  177.         }
  178.         iterator& operator+= (difference_type n)
  179.         {
  180.             difference_type offset = n + (current - first);
  181.             difference_type num_node_to_jump = offset >= 0
  182.                 ? offset / buffer_size()
  183.                 : -((-offset + buffer_size() - 1) / buffer_size());
  184.             if (num_node_to_jump == 0)
  185.                 current += n;
  186.             else
  187.             {
  188.                 node = node + num_node_to_jump;
  189.                 first = *node;
  190.                 last = first + buffer_size();
  191.                 current = first + (offset - num_node_to_jump * buffer_size());
  192.             }
  193.             return *this;
  194.         }
  195.         iterator& operator-= (difference_type n) { return *this += -n; }
  196.         iterator operator+ (difference_type n) const
  197.         {
  198.             iterator tmp = *this; return tmp += n;
  199.         }
  200.         iterator operator- (difference_type n) const
  201.         {
  202.             iterator tmp = *this; return tmp -= n;
  203.         }
  204.         reference operator[] (difference_type n) { return *(*this + n); }
  205.         bool operator== (const iterator& x) const
  206.         {
  207.             return current == x.current ||
  208.                 ((current == first || x.current == x.first) &&
  209.                  *this - x == 0);
  210.         }
  211.         bool operator< (const iterator& x) const
  212.         {
  213.             return (node == x.node) ? (current < x.current) : (node < x.node);
  214.         }
  215.     };  // End of nested definiton of iterator.
  216.  
  217.     //
  218.     // Definition of our constant iterator.
  219.     //
  220.     class const_iterator : public random_access_iterator<T, difference_type>
  221.     {
  222.         friend class deque<T>;
  223.  
  224.       protected:
  225.  
  226.         pointer     current;
  227.         pointer     first;
  228.         pointer     last;
  229.         map_pointer node;
  230.  
  231.         const_iterator (pointer x, map_pointer y)
  232.             : current(x), first(*y), last(*y + buffer_size()), node(y) {}
  233.  
  234.       public:
  235.  
  236.         const_iterator () : current(0), first(0), last(0), node(0) {}
  237.         const_iterator (const iterator& x)
  238.             : current(x.current), first(x.first), last(x.last), node(x.node) {}
  239.         const_reference operator* () const { return *current; }
  240.         difference_type operator- (const cons